package com.itheima.Array.sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

class QuickSort {
    public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int r = partition(nums, start, end);
        quickSort(nums, start, r - 1);
        quickSort(nums, r + 1, end);
    }

    private static int partition(int[] nums, int start, int end) {
        int mark = nums[start];
        int l = start + 1, r = end;
        while (l <= r) {
            while (l <= r && nums[l] <= mark) //1
                l++;
            while (l <= r && nums[r] >= mark) //2
                r--;
            if (l >= r)//3
                break;
            swap(nums, l, r);//4
        }
        swap(nums, start, r); //5
        return r;//6
    }

    private static void swap(int[] nums, int i1, int i2) {
        int temp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = temp;
    }
}